package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         232,
		Discription: "用栈实现队列",
		Level:       1,
		Labels: map[string]int{
			"栈":  1,
			"队列": 1,
		},
	})
}
//两个栈，一个正，一个反
//进队的时候直接进正栈
//出队的时候，首先看反栈有没元素，有的话直接弹出；没有的话把正栈里的元素挨个弹出再进到反栈，这样顺序就反了，最后再弹出反栈
type Stack struct {
	s []int
}

func MakeStack() Stack {
	return Stack{}
}

func (stack *Stack) Push(x int) {
	stack.s = append(stack.s, x)
}

func (stack *Stack) IsEmpty() bool {
	return len(stack.s) == 0
}

func (stack *Stack) Top() int {
	return stack.s[len(stack.s)-1]
}

func (stack *Stack) Pop() int {
	val := stack.s[len(stack.s)-1]
	stack.s = stack.s[:len(stack.s)-1]
	return val
}

type MyQueue struct {
	s1 Stack
	s2 Stack
}

func Constructor4() MyQueue {
	return MyQueue{}
}

func (q *MyQueue) Push(x int) {
	q.s1.Push(x)
}

func (q *MyQueue) Pop() int {
	if !q.s2.IsEmpty() {
		return q.s2.Pop()
	}

	for !q.s1.IsEmpty() {
		val := q.s1.Pop()
		q.s2.Push(val)
	}

	return q.s2.Pop()
}

func (q *MyQueue) Peek() int {
	if !q.s2.IsEmpty() {
		return q.s2.Top()
	}

	for !q.s1.IsEmpty() {
		val := q.s1.Pop()
		q.s2.Push(val)
	}

	return q.s2.Top()
}

func (q *MyQueue) Empty() bool {
	return q.s1.IsEmpty() && q.s2.IsEmpty()
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */
